package com.sicheng.lc.周赛.分类.二分or排序;

import java.util.Arrays;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/14 10:52
 */
public class 咒语和药水成功的对数 {
    public static void main(String[] args) {
        //https://leetcode.cn/problems/successful-pairs-of-spells-and-potions/
        咒语和药水成功的对数 solution = new 咒语和药水成功的对数();
        int[] nums1 = {5, 1, 3};
        int[] nums2 = {1, 2, 3, 4, 5};
        System.out.println(Arrays.toString(solution.successfulPairs(nums1, nums2, 7)));

    }

    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        Arrays.sort(potions);

        int count = 0;
        for (int spell : spells) {
            long target = (long) Math.ceil(success * 1.0 / spell);
            if (target > potions[potions.length - 1]) {
                spells[count++] = 0;
            } else {
                int i = binarySearch(potions, (int) target);
                spells[count++] = potions.length - i;
            }
        }

        return spells;
    }

    public int binarySearch(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}
